1. Field of the Invention
The present invention generally relates to dynamic memory allocation and more specifically to parallel dynamic memory allocation using a nested hierarchical heap.
2. Description of the Related Art
The standard C library provides the malloc( ) command, which allocates blocks of memory dynamically from a heap (“the heap” is the term used for the pool of memory available for allocation). Memory blocks may be of any size, and may be allocated and freed repeatedly and in any order. Multiple calls to malloc( ) are guaranteed not to return overlapping memory regions—the memory is “owned” exclusively by the requestor until it is explicitly released through the free( ) command.
Memory allocation poses a problem in parallel programming because of contention arising between multiple consumers (the executing threads) of a single resource (the heap). If two threads access the heap simultaneously and independently, it is possible that both will claim the same region of memory. As the memory region returned by malloc( ) is owned exclusively by the requestor, two threads acquiring the same region would be an error.
A solution of restricting heap access to one thread at a time via a lock results in serialisation of the requests and hence the poorest possible performance. The problem therefore, is to somehow access the heap in a manner which permits parallel execution yet still ensures safe allocation.
Accordingly, what is needed in the art is an improved system and method for allocating memory from a heap for multiple parallel threads so that each thread acquires a separate portion of memory. Importantly, the system and method should also enable defragmentation of the heap when memory is released by the threads so that the memory in the heap does not become divided into small non-contiguous portions over time.